Subject 4: Latency and capacity estimation for a network connection from asymmetric measurements

The goal of this analysis is to estimate the latency and the capacity of two connections. To do it, two datasets of ping logs are available. One from a short on-campus connection :

http://mescal.imag.fr/membres/arnaud.legrand/teaching/2014/RICM4_EP_ping/liglab2.log.gz

and another from a connection to a remote web site that is popular, and therefore has a heavy load :

http://mescal.imag.fr/membres/arnaud.legrand/teaching/2014/RICM4_EP_ping/stackoverflow.log.gz.

The initial data is formatted like below :

readLines('data/liglab2.log', n=2);

[1] "[1421761682.052172] 665 bytes from lig-publig.imag.fr (129.88.11.7): icmp_seq=1 ttl=60 time=22.5 ms" 
[2] "[1421761682.277315] 1373 bytes from lig-publig.imag.fr (129.88.11.7): icmp_seq=1 ttl=60 time=21.2 ms"

prepare_data.sh formats the logs in csv and removes incorrect lines.

---

To format logs, execute prepare_data.sh script. Formatted files will be saved in the data/ directory.

WARNING : liglab2.log and stackoverflow.log must be placed in data/ directory.

---

First dataset

The first dataset is called liglab2.csv, and has been converted from the liblab2.log.

Data verification

Reading the data

data <- read.csv(file="./data/liglab2.csv", header=TRUE, sep=" ");

Checking that header and first data seems corrects.

# Header
colnames(data)

[1] "date" "size" "time"

#First rows of the dataset
head(data)

We can convert the date timestamp to a more readable format, and check if the data is in a correct format.

data$date = anytime(data$date);

# Check if date has been successfully converted in POSIX dates
class(data$date);

[1] "POSIXct" "POSIXt" 

#Size should be integer
class(data$size);

[1] "integer"

#time should be at least numeric
class(data$time);

[1] "numeric"

Are there any missing data?

na_records = apply(data, 1, function (x) any(is.na(x)))
data[na_records,]

Analysis

Plot the time variation versus date could reveal patterns. Plotly allows to zoom dynamically in the data, which is convenient to explore data.

p <- plot_ly(data, x = ~date, mode='lines')%>%
add_trace(y = ~time, name = "date", type="scatter", mode = 'lines');
p

But in this case, there is not any easily predictible pattern.

There may be also correlation between the size of a packet and its size. But a value in [-0.2, 0.2] doesn’t prove any link between two parameters.

cor(subset(data, select=c("size", "time")));

          size      time
size 1.0000000 0.1802414
time 0.1802414 1.0000000

There is no evident correlation between time of response and packet size. Let’s plot the data to have a more general point of view.

ggplot(data = data, mapping = aes(x =size, y = time))+
  geom_point(size=1)+ ggtitle("Ping time according to packet size")

Thanks to this plot, two classes can be easily seen. The packets which have a size below about 1450-1500 bytes, and the others. To be more precise, there is a zoom in the specified zone.

ggplot(data = data, mapping = aes(x =size, y = time))+
geom_point(size=1)+
coord_cartesian(xlim=c(1450,1500))+ ggtitle("Ping time with a zoom on packet size of ~ 1480 bytes")

According to this set of data, the size delimiter between the two classes would be 1481. The difference between the two classes time could be explained by fragmentation. When a packet reaches a limit size (MTU), it is fragmented in smaller ones. The receiver also has to wait every packets, merge them and respond to the ping, which costs time.

Nevertheless, this way of showing the data can be a bit confusing, because overlapping points and a single point have the same appearance. Sometimes, the geom_count option could solve this problem, but it is not really our case :

ggplot(data = data, mapping = aes(x =size, y = time))+
geom_count() + ggtitle("Ping time according to packet size")

Points are too close from each other. A bit of transparency could be better. To make it more readable, let’s plot both classes separately with a zoom on lower bound.

# Packets whose size is < 1481
low_size = subset(data, size < 1481);

# Packets whose size is >= 1481
high_size = subset(data, size >= 1481);

# Zooming in lower bounds.
p_low <- ggplot(data = low_size, mapping = aes(x =size,y = time)) +
              geom_point(alpha= 0.1)+ggtitle("Ping delays of packets \nwhose size < 1481") + ylim(0,100)
p_high <- ggplot(data = high_size, mapping = aes(x =size, y = time)) +
              geom_point(alpha= 0.1)+ ggtitle("Ping delays of packets \nwhose size >= 1481")
grid.arrange(p_low, p_high, nrow = 1)

It is way more effective. Thanks to this representation, we can see that a most of times are near zero. This is validated by basic stastistics with the sumarry command.

summary(low_size$time);

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  1.000   1.240   1.350   3.517   1.490 276.000 

summary(high_size$time);

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  2.030   2.250   2.320   9.789   2.450 187.000 

Histogram are also useful to have an idea of the times repartition. Despite very high maximum, the 3rd quartile values show that most of times are extremely low (~2ms). Therefore, a thin binwidth is needed.

p_low <- ggplot(data = low_size, mapping = aes(x =time)) +
              geom_histogram(binwidth=2) + ggtitle("Time frequency of packet \nwhose size < 1481")
p_high <- ggplot(data = high_size, mapping = aes(x =time)) +
              geom_histogram(binwidth=2)+ggtitle("Time frequency of packet \nwhose size >= 1481")
grid.arrange(p_low, p_high, nrow = 1)

Most of the times are about 0~2 ms.

Let’s use linear regression to determine the latency (L), and the capacity (C), with the formula \(T(S) = L + \frac{1}{C} * S\). The linear regression allows to predict y when only x is known, with the following equation \(y = \beta_{1} + \beta_{2}x\), where \(\beta_{1}\) is the intercept, and \(\beta_{2}\) is the slope.

In the current case, \(\beta_{1}\) would be \(L\), and \(\beta_{2}\) would be \(\frac{1}{C}\)

p <- ggplot(data = data, mapping = aes(x =size, y = time))+
geom_point(alpha=0.1) + geom_smooth(data=subset(data, size >= 1481), method="lm", size=1.5, aes(colour="Second class linear reg"))+ ylim(0,100) +
geom_smooth(data=subset(data, size < 1481), method="lm", size=1.5, aes(colour="First class linear reg")) + ggtitle("Ping time according to packet size with linear regressions")
p

For the first class of data, the low value of R squared does not means that the model is bad. In our case, it could significate that there is a high variability, which is visible in the previous plot. Standard error are low, but it seams that the intercept value is a bit too high to be realistic. The coefficient is approximately 3.2, which is greater than the 3rd quartile of the dataset. This is caused by the small number of long responses, which have a huge impact on the regression.

# Linear regression of packet size < 1481
linear_reg <- lm(time ~ size, # regression formula
                data=low_size) # data set
summary(linear_reg);

Call:
lm(formula = time ~ size, data = low_size)

Residuals:
    Min      1Q  Median      3Q     Max 
 -2.475  -2.247  -2.189  -2.088 272.489 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 3.276e+00  7.231e-02  45.301  < 2e-16 ***
size        3.263e-04  8.497e-05   3.841 0.000123 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 6.432 on 32665 degrees of freedom
Multiple R-squared:  0.0004514, Adjusted R-squared:  0.0004208 
F-statistic: 14.75 on 1 and 32665 DF,  p-value: 0.000123

For the second class, the linear regression is totally inappropriate, the slope, the standard error and R-squared are bad.

# Linear regression of packet size >= 1481
linear_reg <- lm(time ~ size, # regression formula
                data=high_size) # data set
summary(linear_reg);

Call:
lm(formula = time ~ size, data = high_size)

Residuals:
    Min      1Q  Median      3Q     Max 
 -8.276  -7.729  -7.354  -6.999 177.215 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)  
(Intercept) 5.289833   2.244269   2.357   0.0184 *
size        0.002579   0.001281   2.012   0.0442 *
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 20.74 on 11367 degrees of freedom
Multiple R-squared:  0.0003562, Adjusted R-squared:  0.0002682 
F-statistic:  4.05 on 1 and 11367 DF,  p-value: 0.0442

A quantile regression should be more accurate. Testing different taus could help deciding which percentage of times to take (https://data.library.virginia.edu/getting-started-with-quantile-regression/) Each black dot is the slope coefficient for the quantile indicated on the x axis. The red lines are the least squares estimate and its confidence interval. Uper quantile is well beyond the least squares. A tau of 0.8 could be suitable, and ensures the previous results.

rqfit <- rq(time ~ size, data = low_size, tau=1:9/10)
plot(summary(rqfit), parm="size", main="Size coefficient along with confidence intervals for each tau (Low class)")

rqfit <- rq(time ~ size, data = high_size, tau=1:9/10)
plot(summary(rqfit), parm="size", main="Size coefficient along with confidence intervals for each tau (High class)")

Visually, this quantile regression seems way better than the linear one.

p <- ggplot(data = data, mapping = aes(x =size, y = time))+
geom_point(alpha=0.2) +
geom_quantile(quantiles = 0.8, data=low_size, colour = "blue", size = 2)+
geom_quantile(quantiles = 0.8, data=high_size, colour = "red", size = 2) + ylim(0,100) + ggtitle("Ping time according to packet size with quantile regressions")
p

The extremely low p-value and standard error seems to confirm the graphical result.

# Low class quantile regression
summary(lm(time ~ size, data=low_size[low_size$time < quantile(low_size$time, 0.8),]));

Call:
lm(formula = time ~ size, data = low_size[low_size$time < quantile(low_size$time, 
    0.8), ])

Residuals:
     Min       1Q   Median       3Q      Max 
-0.21996 -0.04801 -0.00938  0.03693  0.38633 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 1.145e+00  8.740e-04  1310.0   <2e-16 ***
size        2.235e-04  1.051e-06   212.7   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.07029 on 26081 degrees of freedom
Multiple R-squared:  0.6343,    Adjusted R-squared:  0.6343 
F-statistic: 4.523e+04 on 1 and 26081 DF,  p-value: < 2.2e-16

# High class quantile regression
summary(lm(time ~ size, data=high_size[high_size$time < quantile(high_size$time, 0.8),]));

Call:
lm(formula = time ~ size, data = high_size[high_size$time < quantile(high_size$time, 
    0.8), ])

Residuals:
      Min        1Q    Median        3Q       Max 
-0.227738 -0.059902 -0.005723  0.049949  0.296367 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 1.904e+00  1.005e-02  189.38   <2e-16 ***
size        2.239e-04  5.748e-06   38.95   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.08342 on 9089 degrees of freedom
Multiple R-squared:  0.143, Adjusted R-squared:  0.1429 
F-statistic:  1517 on 1 and 9089 DF,  p-value: < 2.2e-16

According to the intercept and size estimation, for the first class : the latency \(L\) is approximately equal to \(1.145 * 10^-3\) seconds, and the capacity \(C\) to \(\frac{1}{0.0002235} \simeq 4474\) bytes/s.

For the second class, \(L \simeq 1.9 * 10^-3\) seconds and \(C \simeq \frac{1}{0.0002239} = \simeq 4466\) bytes/s. The capacity doesn’t really change, which is pretty logical, and the latency quite increases with the fragmentation of the package.

Second dataset

The second dataset is called stackoverflow.csv, and has been converted from the stackoverflow.log. It results from a connection to a remote web site connection with heavy loads.

Data verification

The first steps are similar to the first dataset. Thus, they are not detailed.

data <- read.csv(file="./data/stackoverflow.csv", header=TRUE, sep=" ");

# Header
colnames(data)

[1] "date" "size" "time"

# First rows 
head(data)

data$date = anytime(data$date);

# Check if date has been successfully converted in POSIX dates
class(data$date);

[1] "POSIXct" "POSIXt" 

#Size should be integer
class(data$size);

[1] "integer"

#time should be at least numeric
class(data$time);

[1] "integer"

na_records = apply(data, 1, function (x) any(is.na(x)))
data[na_records,]

Analysis

Thanks to this plot, we can see that the gap between extreme values is less important. Like the first set, a predictible pattern could be a bit tough to detect.

p <- plot_ly(data, x = ~date, mode='lines')%>%
add_trace(y = ~time, name = "date", type="scatter", mode = 'lines');
p

The server being far away, the minimum time value for a ping is bigger.

summary(data[["time"]]);

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  110.0   111.0   111.0   114.2   112.0   163.0 

There is even less correlation between size and times.

cor(subset(data, select=c("size", "time")));

      size  time
size 1.000 0.152
time 0.152 1.000

Let’s plot the data to have a more general point of view.

ggplot(data = data, mapping = aes(x =size, y = time))+
geom_point(alpha=0.1) + ggtitle("Ping times according to packet size")

Without any surprise, there is the same average delimitation between packets whose size is below or greater than 1482 bytes. The protocol used is the same, whatever the distance between clients and the web server.

ggplot(data = data, mapping = aes(x =size, y = time))+
geom_point(alpha=0.3)+
coord_cartesian(xlim=c(1450,1500)) + ggtitle("Ping time with a zoom on packet size of ~ 1480 bytes")

Like the short connection, most times are gathered at lower bounds. Nevertheless, we can see with histograms that outliers are more equally distributed than in the first dataset. In addition to fragmentation, waiting time on the server could be increased by heavy load, creating requests queues. If the initial ICMP packet is divided into multiple ones (fragmentation), then packets could arrive at different time, and be far from each other in this queue, which could explain the time difference between small and big packets.

# Packets whose size is < 1482
low_size = subset(data, size < 1482);

# Packets whose size is >= 1482
high_size = subset(data, size >= 1482);

p_low <- ggplot(data = low_size, mapping = aes(x =time)) +
              geom_histogram(binwidth=2) + ggtitle("Time frequency of packet \nwhose size < 1482")
p_high <- ggplot(data = high_size, mapping = aes(x =time)) +
              geom_histogram(binwidth=2)+ggtitle("Time frequency of packet \nwhose size >= 1482")
grid.arrange(p_low, p_high, nrow = 1)

The linear regression seems also inappropriate, including the small number of higher times. The explanations are the same as the first dataset ones.

p <- ggplot(data = data, mapping = aes(x =size, y = time))+
geom_point(alpha=0.3) + geom_smooth(data=subset(data, size >= 1480), method="lm", size=1.5, aes(colour="Second class linear reg"))+
geom_smooth(data=subset(data, size < 1480), method="lm", size=1.5, aes(colour="First class linear reg"))+ ggtitle("Ping time according to packet size with linear regressions")
p

# Linear regression of packet size < 1482
linear_reg <- lm(time ~ size, # regression formula
                data=low_size) # data set
summary(linear_reg);

Call:
lm(formula = time ~ size, data = low_size)

Residuals:
   Min     1Q Median     3Q    Max 
-3.264 -2.277 -2.255 -2.231 36.767 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 1.132e+02  1.653e-01 684.992   <2e-16 ***
size        4.785e-05  1.934e-04   0.247    0.805    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 5.815 on 5019 degrees of freedom
Multiple R-squared:  1.22e-05,  Adjusted R-squared:  -0.000187 
F-statistic: 0.06124 on 1 and 5019 DF,  p-value: 0.8046

# Linear regression of packet size >= 1482
linear_reg <- lm(time ~ size, # regression formula
                data=high_size) # data set
summary(linear_reg);

Call:
lm(formula = time ~ size, data = high_size)

Residuals:
   Min     1Q Median     3Q    Max 
-6.427 -5.136 -4.791 -4.447 45.683 

Coefficients:
              Estimate Std. Error t value Pr(>|t|)    
(Intercept) 120.294063   3.210137  37.473   <2e-16 ***
size         -0.001934   0.001838  -1.052    0.293    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 11.9 on 1801 degrees of freedom
Multiple R-squared:  0.0006144, Adjusted R-squared:  5.953e-05 
F-statistic: 1.107 on 1 and 1801 DF,  p-value: 0.2928

Both visually and numerically with p-value and r-squared, this linear regression seems inappropriate.

A quantile regression should be more accurate. The range between the 3rd quartile and the minimum value of time is the same for packets whose size is below 1482, and only one for the others. Then, a 3rd quartile regression should be perfect to approximate latency and capacity.

#
summary(low_size[["time"]]);

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  110.0   111.0   111.0   113.3   111.0   150.0 

summary(high_size[["time"]]);

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  111.0   112.0   112.0   116.9   112.0   163.0 

p <- ggplot(data = data, mapping = aes(x =size, y = time))+
geom_point(alpha=0.2) + geom_quantile(quantiles = 0.75, data=high_size, colour = "red", size = 2) +
geom_quantile(quantiles = 0.75, data=low_size, colour = "blue", size = 2) + ggtitle("Ping time according to packet size with quantile regressions")
p

Results seem pretty good. The size coefficients in both quantiles regression below don’t allow to reject the null hypothesis. It is hard to compute the capacity C because of this uncertainty. The (Intercept) coefficient has an extremely low standard error, and is estimated at 110 ms.

# Low class 3r quartile regression
summary(lm(time ~ size, data=low_size[low_size$time < quantile(low_size$time, 0.75),]));

Call:
lm(formula = time ~ size, data = low_size[low_size$time < quantile(low_size$time, 
    0.75), ])

Residuals:
       Min         1Q     Median         3Q        Max 
-3.996e-12  1.580e-14  1.640e-14  1.690e-14  1.740e-14 

Coefficients:
             Estimate Std. Error   t value Pr(>|t|)    
(Intercept) 1.100e+02  3.154e-14 3.487e+15   <2e-16 ***
size        4.002e-18  9.151e-17 4.400e-02    0.965    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.563e-13 on 244 degrees of freedom
Multiple R-squared:  0.4995,    Adjusted R-squared:  0.4974 
F-statistic: 243.5 on 1 and 244 DF,  p-value: < 2.2e-16

# High class 3rd quartile regression
summary(lm(time ~ size, data=high_size[high_size$time < quantile(high_size$time, 0.75),]));

Call:
lm(formula = time ~ size, data = high_size[high_size$time < quantile(high_size$time, 
    0.75), ])

Residuals:
       Min         1Q     Median         3Q        Max 
-3.460e-14 -2.884e-14 -1.731e-14 -1.940e-15  1.046e-12 

Coefficients:
              Estimate Std. Error    t value Pr(>|t|)    
(Intercept)  1.110e+02  2.487e-13  4.464e+14   <2e-16 ***
size        -1.601e-16  1.548e-16 -1.034e+00    0.305    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.278e-13 on 69 degrees of freedom
Multiple R-squared:  0.5021,    Adjusted R-squared:  0.4949 
F-statistic: 69.58 on 1 and 69 DF,  p-value: 4.751e-12

The second dataset shows long distance latencies. In contrary to the first dataset, the latencies are the same for the two classes (~110 ms), because the time involved by the data travel is far superior to the packets fragmentation cost. Moreover, the fact that size doesn’t influence at all ping time for the three first quartiles makes the analysis of the capacity not relevant.in this scenario.

Conclusion

The most important point of this analysis to remember, could be that displaying only summaries or simple linear regression isn’t sufficient. The first dataset’s linear regression had great coefficients statistics. It is only after displaying the data that a suitable analysis could be done.

Latencies have been evaluated for each dataset. Nevertheless, the capacity could not be evaluated on long distance connection.